'''
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2
'''
#先尝试使用列表:效率太低
def stRemaining(n,m):
    Recur = list(range(0, n))
    m -= 1
    length = len(Recur)
    while length > 1:
        index = m % length
        Recur = Recur[index + 1:] + Recur[:index]
        length -= 1
    return Recur[0]

def func(n,m):
    '''
    以n=5，m=3 为例
如果把5个数组成列表，那么到得出最后一个值为3的时候，这个值的索引就是0，也就是是这个列表的第0个数。
倒数第二步的时候，列表有两个数，是1、3，此时3的索引是1，即（0+3）% 2，0来源于最后一步3的索引，3为m的值
倒数第三步，列表里有三个数，是1、3、4，此时3的索引是1，即（1+3）% 3， 1来源以倒数第二步3的索引，3为m的值；
以此类推，到第一步，0、1、2、3、4、5，此时3的索引是3，即（上一步的索引 + 3）% n，
总计计算n-1步，从2到n。
    '''
    f = 0
    for i in range(2, n + 1):
        f = (m + f) % i
    return f
def func2(n,m):
    if n == 0:
        return 0
    x = func2(n - 1, m)
    return (m + x) % n

if __name__ == '__main__':
    # print(stRemaining(10, 17))
    print(func(10,17))

